#pragma once
#include "common.h"
void _MergeSort(vector<int>& nums, int l, int r, vector<int>& tmp) {
    if (l >= r) {
        return;
    }
    int mid = l + (r - l) / 2;
    _MergeSort(nums, l, mid, tmp);
    _MergeSort(nums, mid + 1, r, tmp);
    int i = l, j = mid + 1;
    int k = 0;
    while (i <= mid || j <= r) {
        if (i > mid) {
            tmp[k] = nums[j++];
        }
        else if (j > r) {
            tmp[k] = nums[i++];
        }
        else {
            if (nums[i] < nums[j]) {
                tmp[k] = nums[i++];
            }
            else {
                tmp[k] = nums[j++];
            }
        }
        ++k;
    }
    // std::copy(tmp.begin(), tmp.begin() + k, nums.begin() + l, nums.begin() + r);
    for (int i = 0; i < k; ++i) {
        nums[l + i] = tmp[i];
    }
}


void MergeSort(vector<int>& nums) {
    vector<int> tmp(nums.size());
    _MergeSort(nums, 0, nums.size() - 1, tmp);
}